import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class t1022 {
    //从根到叶的二进制数之和
    static ArrayList<String> list = new ArrayList<>();

    public static void main(String[] args) {
        int arr[] = {1,0,1,0,1,0,1};
        TreeNode tree = getTree(arr);
        showTree(tree);
        //TreeNode node = new TreeNode();//653  TreeNode
        int i = sumRootToLeaf(tree);
        System.out.println(i);

    }
    public static int sumRootToLeaf(TreeNode root){
      return dfs(root,0);
    }
    public static int dfs(TreeNode root,int val){
        if(root==null){
            return 0;
        }
        val = (val<<1) | root.val;
        if(root.left==null && root.right==null){
            return val;
        }
        return dfs(root.left,val)+dfs(root.right,val);
    }
    public static TreeNode getTree(int arr[]){
        TreeNode root = new TreeNode(arr[0]);
        TreeNode tmp = root;
        Queue<TreeNode> queue = new LinkedList<>();
        int i =0;
        while (tmp!=null){
            if(2*i+1<arr.length){
                tmp.left = new TreeNode(arr[2*i+1]);
                queue.add(tmp.left);
            }
            if(2*i+2<arr.length){
                tmp.right = new TreeNode(arr[2*i+2]);
                queue.add(tmp.right);
            }
            i++;
            tmp = queue.poll();
        }
        return root;
    }
    public static void showTree(TreeNode Tree){
        Queue<TreeNode> queue = new LinkedList<>();
        while (Tree!=null){
            System.out.print(Tree.val+" ");
            if(Tree.left!=null){
                queue.add(Tree.left);
            }
            if(Tree.right!=null){
                queue.add(Tree.right);
            }
            Tree=queue.poll();
        }

    }
}


